package algo.A03_递归和算法复杂度;

public class T14_求a的n次幂 {
    public static void main(String[] args) {
        int a = 2;
        int n = 30;
        int answer = (int) Math.pow(a, n);
        System.out.println("answer = " + answer);
        int result01 = solution01(a, n);
        System.out.println("result01 = " + result01);
        int result02 = solution02(a, n);
        System.out.println("result02 = " + result02);
    }

    /**
     * for循环法 时间复杂度O(n)
     *
     * @param a 底数
     * @param n 指数
     * @return a^n
     */
    private static int solution01(int a, int n) {
        int result = 1;
        for (int i = 0; i < n; i++) {
            result *= a;
        }
        return result;
    }

    /**
     * 快捷方法：例如计算2的15次方，则直接2*2=4(2^2)，4*4=16(2^4)，16*16=256(2^8)，然后递归计算剩下的7次方
     *
     * @param a
     * @param n
     * @return
     */
    private static int solution02(int a, int n) {
        if (n == 0) {
            return 1;
        }
        int result = a;
        int ex = 1;//记录指数部分
        //指数*2大于n时，说明不能继续翻一番了
        while (ex * 2 <= n) {
            //翻一番
            result = result * result;
            //指数
            ex = ex * 2;//指数部分乘以2
        }
        return result * solution02(a, n - ex);
    }


}
